home *** CD-ROM | disk | FTP | other *** search
/ BBS in a Box 7 / BBS in a Box - Macintosh - Volume VII (BBS in a Box) (January 1993).iso / Files / Prog / M / Mac gperf 1.9.cpt / Mac gperf 1.9 / src / hashtable.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-03-09  |  4.2 KB  |  142 lines  |  [TEXT/KAHL]
  1. /* Hash table for checking keyword links.  Implemented using double hashing.
  2.    Copyright (C) 1989 Free Software Foundation, Inc.
  3.    written by Douglas C. Schmidt (schmidt@ics.uci.edu)
  4.  
  5. This file is part of GNU GPERF.
  6.  
  7. GNU GPERF is free software; you can redistribute it and/or modify
  8. it under the terms of the GNU General Public License as published by
  9. the Free Software Foundation; either version 1, or (at your option)
  10. any later version.
  11.  
  12. GNU GPERF is distributed in the hope that it will be useful,
  13. but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15. GNU General Public License for more details.
  16.  
  17. You should have received a copy of the GNU General Public License
  18. along with GNU GPERF; see the file COPYING.  If not, write to
  19. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  20.  
  21. #include <stdio.h>
  22. #include <string.h>
  23.  
  24. #include "options.h"
  25. #include "xmalloc.h"
  26.  
  27. #include "hashtable.h"
  28.  
  29.     /* Locally visible hash table. */
  30.     
  31. static HASH_TABLE hash_table;
  32.  
  33. #define POW(X) ((!X)?1:(X-=1,X|=X>>1,X|=X>>2,X|=X>>4,X|=X>>8,X|=X>>16,(++X)))
  34.  
  35. static unsigned int hash_pjw( char * str );
  36.  
  37.  
  38.     /***********************************************************************\
  39.     *                                                                        *
  40.     * name:        hash_pjw                                                    *
  41.     *                                                                        *
  42.     * descr:    Hash identifier                                                *
  43.     *                                                                        *
  44.     \***********************************************************************/
  45.  
  46. static unsigned int hash_pjw( char * str )
  47. {
  48.     char *            temp;
  49.     unsigned int    g;
  50.     unsigned int    h = 0;
  51.  
  52.     for ( temp = str; *temp; temp++ ) 
  53.     {
  54.         h = ( h << 4 ) + ( *temp * 13 );
  55.         if ( g = h & 0xf0000000 )
  56.         {
  57.             h ^= ( g >> 24 );
  58.             h ^= g;
  59.         }
  60.     }
  61.  
  62.     return h;
  63. }
  64.  
  65.     /***********************************************************************\
  66.     *                                                                        *
  67.     * name:        hash_table_init                                                *
  68.     *                                                                        *
  69.     * descr:    Initialize the hash table.                                    *
  70.     *                                                                        *
  71.     \***********************************************************************/
  72.  
  73. /* The size of the hash table is always the smallest power of 2 >= the size
  74.    indicated by the user.  this allows several optimizations, including
  75.    the use of double hashing and elimination of the mod instruction.
  76.    note that the size had better be larger than the number of items
  77.    in the hash table, else there's trouble!!! */
  78.  
  79. void hash_table_init( int s )
  80. {
  81.     hash_table.size        = POW (s);
  82.     hash_table.table    = (LIST_NODE **) xmalloc( hash_table.size * sizeof(*hash_table.table) );
  83.     memset( hash_table.table, 0, hash_table.size * sizeof(*hash_table.table) );
  84. }
  85.  
  86.     /***********************************************************************\
  87.     *                                                                        *
  88.     * name:        hash_table_destroy                                            *
  89.     *                                                                        *
  90.     * descr:    Frees the dynamically allocated table.                        *
  91.     *                                                                        *
  92.     \***********************************************************************/
  93.  
  94. void hash_table_destroy()
  95. { 
  96.     if ( OPTION_ENABLED( option, DEBUG ) )
  97.     {
  98.         int        i;
  99.  
  100.         fprintf( stderr, "\ndumping the hash table\n" );
  101.  
  102.         for ( i = hash_table.size - 1; i >= 0; i-- )
  103.             if ( hash_table.table[i] )
  104.                 fprintf( stderr, "location[%d] = key set %s, key %s\n",
  105.                             i, hash_table.table[i]->key_set, hash_table.table[i]->key);
  106.  
  107.         fprintf( stderr, "end dumping hash table\n\n" );
  108.     }
  109. }
  110.  
  111.     /***********************************************************************\
  112.     *                                                                        *
  113.     * name:        retrieve                                                    *
  114.     *                                                                        *
  115.     * descr:    If the item is already in the hash table, return the         *
  116.     *            item found in the table. Otherwise, insert the item and     *
  117.     *            return false. Use double hashing.                            *
  118.     *                                                                        *
  119.     \***********************************************************************/
  120.  
  121. LIST_NODE * retrieve( LIST_NODE * item, int ignore_length )
  122. {
  123.     unsigned int    hash_val    = hash_pjw( item->key_set );
  124.     int                probe        = hash_val & hash_table.size - 1;
  125.     int                increment    = ( hash_val ^ item->length | 1 ) & hash_table.size - 1;
  126.   
  127.     while ( hash_table.table[probe]
  128.             && ( strcmp( hash_table.table[probe]->key_set, item->key_set )
  129.                 || ( !ignore_length && hash_table.table[probe]->length != item->length ) ) )
  130.     {
  131.         probe = probe + increment & hash_table.size - 1;
  132.     }
  133.  
  134.     if ( hash_table.table[probe] )
  135.         return hash_table.table[probe];
  136.     else
  137.     {
  138.         hash_table.table[probe] = item;
  139.         return 0;
  140.     }
  141. }
  142.